package a1sort.a1insertionsort;

import java.util.Arrays;
import java.util.Random;
/**
 * @description
 * 插入排序-参考算法导论第二章第一小节
 * 运行时间Θ(n²)
 * @author zhangMr
 * **/
public class InsertionSort {
    public static void InsertionSort(Integer[] data){
        for(int j=1;j<data.length;j++){
            Integer key=data[j];
            Integer i=j-1;
            while(i>=0&&data[i].intValue()>key.intValue()){
                data[i+1]=data[i];
                i--;
            }
            data[i+1]=key;
        }
    }

    public static void main(String[] args) {
        Random random=new Random();
        Integer[]data=new Integer[10];
        for(int i=0;i<10;i++){
            data[i]= random.nextInt(100);
        }
        System.out.println("随机生成的数组"+Arrays.toString(data));
        InsertionSort(data);
        System.out.println("排序后的数组"+Arrays.toString(data));
    }
}
